package jianzhioffer.list;

import algorithm.model.ListNode;

/**
 * 两个链表的第一个公共节点
 * 思路：
 * @See: src.main.java.algorithm.linkedlist#IntersectionOfTwoLinkedLists
 *
 * Created by yzy on 2020-06-11 16:00
 */
public class FindFirstCommonNode {

    public static void main(String[] args) {
        ListNode commonNode = ListNode.initDate(new int[]{3,4,5});
        ListNode n1 = ListNode.initDate(new int[]{11,12});
        ListNode n2 = ListNode.initDate(new int[]{13,14});
        n1.next = commonNode;
        n2.next = commonNode;

        ListNode firstCommonNode = findFirstCommonNode(n1, n2);
        System.out.println(firstCommonNode);
    }


    /**
     * 指针法，找到两个链表长度，移动较长的那个链表指针到相同长度，然后一起往下遍历并比较，如果相等则为第一个交点。
     * 空间复杂度N(1)
     * @param pHead1
     * @param pHead2
     * @return
     */
    public static ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1 = 0;
        int len2 = 0;
        ListNode dummy1 = pHead1;
        ListNode dummy2 = pHead2;
        while(dummy1 != null){
            len1++;
            dummy1 = dummy1.next;
        }
        while(dummy2 != null){
            len2++;
            dummy2 = dummy2.next;
        }

        int diffLen = len1 - len2;
        ListNode tmpNode = diffLen > 0 ? pHead1 : pHead2;
        ListNode waitNode = diffLen > 0 ? pHead2 : pHead1;
        diffLen = Math.abs(diffLen);
        while(diffLen > 0){
            tmpNode = tmpNode.next;
            diffLen--;
        }

        while(tmpNode != null && waitNode != null){
            if(tmpNode == waitNode){
                return tmpNode;
            }
            tmpNode = tmpNode.next;
            waitNode = waitNode.next;
        }

        return null;
    }
}
